package leetcode101.search_problem.bfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code8
 * @Description 310. 最小高度树
 * 树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
 *
 * 给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），
 * 其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
 *
 * 可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
 *
 * 请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
 *
 * 树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-08 10:58
 */
public class Code8 {
    public static void main(String[] args) {
        int[][] edges = new int[][] {{3,0},{3,1},{3,2},{3,4},{5,4}};
        findMinHeightTrees(6, edges);
    }
    public static List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if (n == 1) {
            res.add(0);
            return res;
        }
        /* 建立各个结点的出度表 */
        int[] degree = new int[n];
        /* 建立图关系，在每个节点的List中存储与其相连的结点 */
        List<List<Integer>> map = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            map.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            degree[edge[0]]++;
            degree[edge[1]]++;
            map.get(edge[0]).add(edge[1]);
            map.get(edge[1]).add(edge[0]);
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            res = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int head = queue.poll();
                res.add(head);
                List<Integer> neighbors = map.get(head);
                for (int neighbor : neighbors) {
                    degree[neighbor]--;
                    if (degree[neighbor] == 1) {
                        queue.offer(neighbor);
                    }
                }
            }
        }
        return res;
    }
}
/*
因为最小高度的树可能会出现在任意结点为根的情况，所以想到的可能的解法是
首先将所有结点作为根节点，构建队列进行bfs然后记录最小高度
这样就得到了所有结点作为根结点的最小高度，然后我们从中取最小高度对应的根节点即可。
但是这样做会超时
所以我们可以倒着求，从边缘开始，先找出所有度为1的结点，然后把所有出度为1的结点入队
然后不断地bfs，最后找到地就是两边同时向中间靠近地结点，那么这个中间节点相当于把整个距离二分
自然就是到两边距离最小的点。

大致想法就是，把树看作一个图
每次去掉一圈叶子结点
每次去掉一圈叶子节点
最后丢下那一个或者那两个结点就是最后的结果
反正就是这么回事你想去吧你
 */